/*
 * BinaryHeap.h
 *
 *  Created on: 28/05/2011
 *      Author: frandres
 */

#ifndef BINARYHEAP_H_
#define BINARYHEAP_H_

#include <vector>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include "FifteenPuzzleNodeA.h"
using std::vector;
using std::cout;

/* Esta es una implementación de un Heap Binario que utiliza
 * un vector como estructura de datos.
 *
 * Esto es posible usando la siguiente regla:
 *
 * Para todo elemento i, sus hijos se consiguen en la posición 2i +1
 * y 2i+2.
 *
 * Para todo hijo i, su padre se consigue en la posición piso ((i−1)/2)

*/
class BinaryHeap {
public:
	BinaryHeap();
	virtual ~BinaryHeap();
	int size();
	void insertElement(FifteenPuzzleNodeA * node);
	void removeElement (unsigned int position);
	FifteenPuzzleNodeA * pullMax();
	bool empty();
//private:
	inline unsigned int getFatherIndex(int i);
	inline unsigned int getChildIndex(int i,int j);
	//unsigned int numberElements;
	void upHeap(FifteenPuzzleNodeA * node,int position);
	void downHeap(unsigned int position);
	void swap(unsigned int pos1, unsigned int pos2);
	//vector elements <FifteenPuzzleNodeA *>;
	vector <FifteenPuzzleNodeA *> * elements;
};



#endif /* BINARYHEAP_H_ */
